package leecode

func generateParenthesis(n int) []string {
	size := n * 2
	var result []string
	path := make([]byte, size)
	var dfs func(index, open int)
	dfs = func(index, open int) {
		if index == size {
			temp := make([]byte, size)
			copy(temp, path)
			result = append(result, string(temp))
			return
		}
		//如果左括号的个数小于n
		if open < n {
			path[index] = '('
			dfs(index+1, open+1)
		}
		//如果右括号的个数小于左括号
		if index-open < open {
			path[index] = ')'
			dfs(index+1, open)
		}
	}
	dfs(0, 0)
	return result
}
